package 题目集.动态规划.区间dp;

import java.util.Arrays;

import org.junit.Test;

public class ch01_成为回文串的最小代价 {
	/**
	 * 思路:如果l,r位置不一样,则一定需要在左侧或右侧插入一个.返回两头插入最少的一个 
	 */
    public int minInsertions(String s) {
    	chars=s.toCharArray();
    	dp=new int[chars.length][chars.length];
    	for(int[] d:dp) {
    		Arrays.fill(d, -1);
    	}
    	int ans=dfs(0,chars.length-1);
    	return ans;
    }
    char[] chars;
    int[][] dp;
    public int dfs(int l,int r) {
    	if(dp[l][r]!=-1) {
    		return dp[l][r];
    	}
    	if(l==r) {
    		dp[l][r]=0;
    	}else if(l+1==r) {
    		dp[l][r]=chars[l]==chars[r]?0:1;
    	}else if(chars[l]==chars[r]) {
    		dp[l][r]=dfs(l+1,r-1);
    	}else {
    		int right=dfs(l+1,r);
    		int left=dfs(l,r-1);
    		dp[l][r]=Math.min(left, right)+1;
    	}
    	return dp[l][r];
    }
    
    
    @Test
    public void test() {
    	int ans=minInsertions("123455637");
    	System.out.println(ans);
    } 
}
